﻿#define _CRT_SECURE_NO_WARNINGS
#include <bits/stdc++.h>
using namespace std;

typedef list<int> Container;

int main()
{
	Container cont = { 1, 2, 3, 4, 5 };
	Container::iterator iter, tempIt;
	for (iter = cont.begin(); iter != cont.end();)
	{
		tempIt = iter;
		++iter;
		cont.erase(tempIt);
	}
}

//建立有序表：12，23，46，67，85
//建立有序表：5，59，94
//两个有序顺序表合并为一个有序顺序表，验证代码的正确性。

//#include <stdio.h>
//#include <stdlib.h>
//#include <assert.h>
//
//typedef int SLDataType;
//typedef struct SeqList
//{
//	SLDataType* a;
//	int size;
//	int capacity;
//}SeqList;
//
//void SListInit(SeqList* ps)
//{
//	//assert(ps);
//	ps->size = 0;
//	ps->capacity = 4;
//	ps->a = (SLDataType*)malloc(sizeof(SLDataType) * 4);
//	if (ps->a == NULL)
//	{
//		perror("malloc fail");
//		return;
//	}
//}
//
//void SListDestroy(SeqList* ps)
//{
//	assert(ps);
//	ps->a = NULL;
//	ps->capacity = 0;
//	ps->size = 0;
//}
//
//void SListCheckCapacity(SeqList* ps)
//{
//	assert(ps);
//	if (ps->size == ps->capacity)
//	{
//		SLDataType* tmp = NULL;
//		tmp = (SLDataType*)realloc(ps->a, sizeof(SLDataType) * (ps->capacity) * 2);
//		if (tmp == NULL)
//		{
//			perror("realloc fail");
//			return;
//		}
//		ps->a = tmp;
//		ps->capacity *= 2;
//		//printf("The capacity now:%d\n", ps->capacity);
//	}
//	else
//	{
//		return;
//	}
//}
//
//void SListPushBack(SeqList* ps, SLDataType x)
//{
//	assert(ps);
//	SListCheckCapacity(ps);
//	ps->a[ps->size] = x;
//	ps->size++;
//}
//
//void SListPrint(SeqList* ps)
//{
//	assert(ps);
//	for (int i = 0; i < ps->size; i++)
//	{
//		printf("%d ", ps->a[i]);
//	}
//	printf("\n");
//}
//
//void SListMerge(SeqList* ps1, SeqList* ps2)
//{
//	assert(ps1);
//	assert(ps2);
//	SeqList ps;
//	SListInit(&ps);
//	int cur1 = 0, cur2 = 0;
//	while (cur1 < ps1->size && cur2 < ps2->size)
//	{
//		if (ps1->a[cur1] <= ps2->a[cur2])
//		{
//			SListPushBack(&ps, ps1->a[cur1]);
//			cur1++;
//		}
//		else
//		{
//			SListPushBack(&ps, ps2->a[cur2]);
//			cur2++;
//		}
//	}
//	while (cur1 < ps1->size)
//	{
//		SListPushBack(&ps, ps1->a[cur1]);
//		cur1++;
//	}
//	while (cur2 < ps2->size)
//	{
//		SListPushBack(&ps, ps2->a[cur2]);
//		cur2++;
//	}
//	printf("The result of merging two seqlists is:\n");
//	SListPrint(&ps);
//}
//
//int main()
//{
//	SeqList ps1;
//	SeqList ps2;
//	SListInit(&ps1);
//	SListInit(&ps2);
//	int quantity1 = 0, quantity2 = 0, input = 0;
//
//	printf("Input quantity of seqlist1-> ");
//	scanf("%d", &quantity1);
//	for (int i = 0; i < quantity1; i++)
//	{
//		scanf("%d", &input);
//		SListPushBack(&ps1, input);
//	}
//
//	printf("Input quantity of seqlist2-> ");
//	scanf("%d", &quantity2);
//	for (int i = 0; i < quantity2; i++)
//	{
//		scanf("%d", &input);
//		SListPushBack(&ps2, input);
//	}
//
//	SListMerge(&ps1, &ps2);
//	return 0;
//}


//#include <bits/stdc++.h>
//using namespace std;
//
//
//int cal(int a, int b, char opera)
//{
//	switch (opera)
//	{
//	case '+': return a + b;
//	case '-': return a - b;
//	case '*': return a * b;
//	case '/': return a / b;
//	default: throw invalid_argument("bad opera");
//	}
//}
//
//int calculate(string s)
//{
//	string tmp;
//	for (char i : s)
//	{
//		if (i != ' ')
//		{
//			tmp.push_back(i);
//		}
//	}
//	s = std::move(tmp);
//
//	stack<int> result;
//	stack<char> operas;
//
//	operas.push('+');
//	result.push(0);
//	for (int i = 0; i < s.size();)
//	{
//		if (s[i] >= '0' && s[i] <= '9')
//		{
//			operas.push('+');
//			int val = 0;
//			while (s[i] >= '0' && s[i] <= '9')
//			{
//				val = val * 10 + (s[i] - 48);
//				i++;
//			}
//			result.push(val);
//		}
//		else if (s[i] == '(')
//		{
//			operas.push('+');
//			result.push(-1);
//			i++;
//		}
//		else if (s[i] == ')')
//		{
//			int val = 0;
//			while (result.top() != -1)
//			{
//				val = cal(val, result.top(), operas.top());
//				result.pop(); 
//				operas.pop();
//			}
//			if (operas.top() == '*' || operas.top() == '/')
//			{
//				result.pop();
//				val = cal(result.top(), val, operas.top());
//				operas.pop();
//			}
//
//			if (val >= 0)
//			{
//				result.top() = val;
//			}
//			else
//			{
//				result.top() = -val;
//				if (operas.top() == '+')
//				{
//					operas.top() = '-';
//				}
//				else operas.top() = '+';
//			}
//			i++;
//		}
//		else
//		{
//			char opera = s[i]; i++;
//			if (s[i] == '(')
//			{
//				result.push(-1); i++;
//				operas.push(opera);
//			}
//			else
//			{
//				int val = 0;
//				while (s[i] >= '0' && s[i] <= '9')
//				{
//					val = val * 10 + (s[i] - 48);
//					i++;
//				}
//				if (opera == '*' || opera == '/')
//				{
//					result.top() = cal(result.top(), val, opera);
//				}
//				else
//				{
//					operas.push(opera);
//					result.push(val);
//				}
//			}
//		}
//	}
//	int val = 0;
//	while (!result.empty())
//	{
//		val = cal(val, result.top(), operas.top());
//		result.pop(); operas.pop();
//	}
//
//	return val;
//}
//
//int main()
//{
//	//string s = "(1+(4+5+2)-3)+(6+8)*2";
//	string s;
//	cout << "输入中缀表达式，例如(1+(4+5+2)-3)+(6+8)*2" << endl;
//	cin >> s;
//	cout << calculate(s) << endl;
//	return 0;
//}

//#include <bits/stdc++.h>
//using namespace std;
//int main()
//{
//    int n;
//    cin >> n;
//    vector<int> v(n);
//    for (int i = 0; i < n; i++)
//    {
//        cin >> v[i];
//    }
//    sort(v.begin(), v.end());
//    int max = v[n - 1];
//    int min = v[0];
//    int sum = 0;
//    for (auto ch : v)
//    {
//        if (ch != max && ch != min)
//        {
//            sum += ch;
//        }
//    }
//    cout << sum << endl;
//    // 请在此输入您的代码
//    return 0;
//}
//
//#include <iostream>
//#include <string>
//#include <vector>
//#include <stack>
//#include <queue>
////#include <bits / stdc++.h>
//using namespace std;
//
//class Solution
//{
//public:
//    int minCostClimbingStairs(vector<int>& cost)
//    {
//        int n = cost.size();
//        vector<int> dp(n);
//        dp[n - 1] = cost[n - 1];
//        dp[n - 2] = cost[n - 2];
//
//        for (int i = n - 3; i >= 0; i--)
//        {
//            dp[i] = min(dp[i + 1] + cost[i], dp[i + 2] + cost[i]);
//        }
//
//        return min(dp[0], dp[1]);
//    }
//};

//// 判断是否为质数，是返回true 不是返回false
//bool check(int n)
//{
//	if (n == 0 || n == 1)
//	{
//		return false;
//	}
//	for (int i = 2; i * i <= n; i++)
//	{
//		if (n % i == 0)
//		{
//			return false;
//		}
//	}
//	return true;
//}
//
//int main()
//{
//	int a, b, k;
//	cin >> a >> b >> k;
//	vector<int> nums(b - a + 1);
//	for (int i = 0; i < b - a + 1; i++)
//	{
//		nums[i] = i + a;
//	}
//	int res = 0, len = INT_MIN;
//
//	for (int left = 0, right = 0; right < nums.size(); right++)
//	{
//		// 进窗口
//		if (check(nums[right]))
//		{
//			res++;
//		}
//
//		// 判断
//		while (res  == k)
//		{
//			// 出窗口
//			len = max(right - left + 1, len);
//			if (check(nums[left]))
//			{
//				res--;
//			}
//			left++;
//		}
//	}
//
//	if (len == INT_MIN)
//	{
//		cout << "-1" << endl;
//	}
//	else
//	{
//		cout << len << endl;
//	}
//
//	return 0;
//}

//int lengthOfLongestSubstring(string s)
//{
//    if (s.size() == 1)
//    {
//        return 1;
//    }
//    int left = 0, right = 0, hash[128] = { 0 }, ret = 0;
//    for (left = 0, right = 0; right < s.size(); right++)
//    {
//        // 进窗口
//        hash[s[right]]++;
//
//        // 判断
//        while (hash[s[right]] > 1)
//        {
//            ret = max(ret, right - left);
//            // 出窗口
//            hash[s[left++]]--;
//        }
//    }
//    return ret;
//}

//#include <iostream>
//#include <string>
//#include <vector>
//#include <stack>
//#include <queue>
//using namespace std;
//
//#include <bits/stdc++.h>
//using namespace std;
//
//// 判断是否为质数，是返回true 不是返回false
//bool check(int n)
//{
//    if (n == 0 || n == 1)
//    {
//        return false;
//    }
//    for (int i = 2; i * i <= n; i++)
//    {
//        if (n % i == 0)
//        {
//            return false;
//        }
//    }
//    return true;
//}
//
//int main()
//{
//    int a, b, k;
//    cin >> a >> b >> k;
//    vector<int> nums(b - a + 1);
//    for (int i = 0; i < b - a + 1; i++)
//    {
//        nums[i] = i + a;
//    }
//    int res = 0, len = INT_MIN;
//    for (int left = 0, right = 0; right < nums.size(); right++)
//    {
//        // 进窗口
//        if (check(nums[right]))
//        {
//            res++;
//        }
//
//        // 判断
//        while (res == k)
//        {
//            // 出窗口
//            len = max(right - left + 1, len);
//            if (check(nums[left]))
//            {
//                res--;
//            }
//            left++;
//        }
//    }
//    if (len == INT_MIN)
//    {
//        cout << "-1" << endl;
//    }
//    else
//    {
//        cout << len << endl;
//    }
//    return 0;
//}

//int tribonacci(int n)
//{
//    vector<int> dp(n + 1);
//
//    dp[0] = 0, dp[1] = dp[2] = 1;
//
//    for (int i = 3; i <= n; i++)
//    {
//        dp[i] = dp[i - 1] + dp[i - 2] + dp[i - 3];
//    }
//
//    return dp[n];
//}
//
//int main()
//{
//    cout << tribonacci(0);
//    return 0;
//}

//int main()
//
//{
//
//    queue<char> Q;
//
//    char x, y;
//
//    x = 'n'; y = 'g';
//
//    Q.push(x); Q.push('i'); Q.push(y);
//
//    Q.pop(); Q.push('r'); Q.push('t'); Q.push(x);
//
//    Q.pop(); Q.push('s');
//
//    while (!Q.empty())
//
//    {
//
//        x = Q.front();
//
//        Q.pop();
//
//        cout << x;
//
//    };
//
//    cout << y;
//
//}

//int getrandom(vector<int>& nums, int left, int right)
//{
//	return nums[rand() % (right - left + 1) + left];
//}
//
//void quicksort(vector<int>& nums, int l, int r)
//{
//	if (l >= r)
//	{
//		return;
//	}
//
//	int left = l - 1, right = r + 1, i = l;
//	int key = getrandom(nums, l, r);
//
//	while (i < right)
//	{
//		if (nums[i] < key)
//		{
//			swap(nums[++left], nums[i++]);
//		}
//		else if (nums[i] == key)
//		{
//			i++;
//		}
//		else
//		{
//			swap(nums[--right], nums[i]);
//		}
//	}
//
//	quicksort(nums, l, left);
//	quicksort(nums, right, r);
//}
//
//vector<int> tmp;
//
//void mergesort(vector<int>& nums, int left, int right)
//{
//	if (left >= right)
//	{
//		return;
//	}
//
//	int mid = (left + right) / 2;
//	mergesort(nums, left, mid);
//	mergesort(nums, mid + 1, right);
//
//	int cur1 = left, cur2 = mid + 1, i = 0;
//	while (cur1 <= mid && cur2 <= right)
//	{
//		if (nums[cur1] <= nums[cur2])
//		{
//			tmp[i++] = nums[cur1++];
//		}
//		else
//		{
//			tmp[i++] = nums[cur2++];
//		}
//	}
//
//	while (cur1 <= mid)
//	{
//		tmp[i++] = nums[cur1++];
//	}
//	while (cur2 <= right)
//	{
//		tmp[i++] = nums[cur2++];
//	}
//
//	for (int i = left; i <= right; i++)
//	{
//		nums[i] = tmp[i - left];
//	}
//}
//
//void AdjustDown(vector<int>& nums, int size, int parent)
//{
//	int child = parent * 2 + 1;
//	while (child < size)
//	{
//		if (child + 1 < size && nums[child + 1] > nums[child])
//		{
//			child++;
//		}
//		if (nums[child] > nums[parent])
//		{
//			swap(nums[child], nums[parent]);
//			parent = child;
//			child = parent * 2 + 1;
//		}
//		else
//		{
//			break;
//		}
//	}
//}
//
//void heapsort(vector<int>& nums, int size)
//{
//	for (int i = (size - 1 - 1) / 2; i >= 0; i--)
//	{
//		AdjustDown(nums, size, i);
//	}
//
//	int end = size - 1;
//	while (end > 0)
//	{
//		swap(nums[0], nums[end]);
//		AdjustDown(nums, end, 0);
//		end--;
//	}
//}
// //while (left <= right)
//{
//    int mid = left + (right - left) / 2;
//    if (nums[mid] == target)
//    {
//        return mid;
//    }
//    else if (nums[mid] < target)
//    {
//        left = mid + 1;
//    }
//    else
//    {
//        right = mid - 1;
//    }
//}
//
// 
//int main()
//{
//	vector<int> v1{ 9,8,7,6,5,4,1,2,3 };
//	vector<int> v2{ 9,8,7,6,5,4,1,2,3 };
//	vector<int> v3{ 9,8,7,6,5,4,1,2,3 };
//
//	quicksort(v1, 0, v1.size() - 1);
//	for (auto ch : v1)
//	{
//		cout << ch << " ";
//	}
//	cout << endl;
//
//	tmp.resize(v2.size());
//	mergesort(v2, 0, v2.size() - 1);
//	for (auto ch : v1)
//	{
//		cout << ch << " ";
//	}
//	cout << endl;
//
//	heapsort(v3, v3.size());
//	for (auto ch : v1)
//	{
//		cout << ch << " ";
//	}
//	cout << endl;
//
//	return 0;
//}

//vector<int> tmp;
//
//int getrandom(vector<int>& nums, int left, int right)
//{
//	return nums[rand() % (right - left + 1) + left];
//}
//
//void quicksort(vector<int>& nums, int l, int r)
//{
//	// 1.递归返回条件
//	if (l >= r)
//	{
//		return;
//	}
//
//	// 2.数组分块
//	int left = l - 1, right = r + 1, i = l;
//	int key = getrandom(nums, l, r);
//	while (i < right)
//	{
//		if (nums[i] < key)
//		{
//			swap(nums[++left], nums[i++]);
//		}
//		else if (nums[i] == key)
//		{
//			i++;
//		}
//		else
//		{
//			swap(nums[--right], nums[i]);
//		}
//	}
//
//	// 3.左右区间递归
//	quicksort(nums, l, left - 1);
//	quicksort(nums, right + 1, r);
//}
//
//void mergesort(vector<int>& nums, int left, int right)
//{
//	// 1.递归返回条件
//	if (left >= right)
//	{
//		return;
//	}
//	// 2.整个区间拆分
//	int mid = (left + right) / 2;
//	mergesort(nums, left, mid);
//	mergesort(nums, mid + 1, right);
//
//	// 3.数组排序写入临时数组
//	int cur1 = left, cur2 = mid + 1, i = 0;
//	while (cur1 <= mid && cur2 <= right)
//	{
//		if (nums[cur1] < nums[cur2])
//		{
//			tmp[i++] = nums[cur1++];
//		}
//		else
//		{
//			tmp[i++] = nums[cur2++];
//		}
//	}
//	while (cur1 <= mid)
//	{
//		tmp[i++] = nums[cur1++];
//	}
//	while (cur2 <= right)
//	{
//		tmp[i++] = nums[cur2++];
//	}
//
//	// 4.还原到原数组
//	for (int i = left; i <= right; i++)
//	{
//		nums[i] = tmp[i - left];
//	}
//}
//
//void AdjustDown(vector<int>& nums, int size, int parent)
//{
//	int child = parent * 2 + 1;
//	while (child < size)
//	{
//		if (child + 1 < size && nums[child + 1] > nums[child])
//		{
//			child++;
//		}
//		if (nums[child] > nums[parent])
//		{
//			swap(nums[child], nums[parent]);
//			parent = child;
//			child = parent * 2 + 1;
//		}
//		else
//		{
//			break;
//		}
//	}
//}
//
//void heapsort(vector<int>& nums, int size)
//{
//	// 1.建堆
//	for (int i = (size - 1 - 1) / 2; i >= 0; i--)
//	{
//		AdjustDown(nums, size, i);
//	}
//
//	// 2.堆排序
//	int end = size - 1;
//	while (end > 0)
//	{
//		swap(nums[0], nums[end]);
//		AdjustDown(nums, end, 0);
//		end--;
//	}
//}
//
//int main()
//{
//	srand(time(NULL));
//	vector<int> nums{ 6,5,3,23,4,5,6,6 };
//	//quicksort(nums, 0, nums.size() - 1);
//	tmp.resize(nums.size());
//	//mergesort(nums, 0, nums.size() - 1);
//	heapsort(nums, nums.size());
//	for (auto ch : nums)
//	{
//		cout << ch << " ";
//	}
//	return 0;
//}
//class Solution
//{
//public:
//	vector<int> getLeastNumbers(vector<int>& nums, int k)
//	{
//		srand(time(NULL));
//		quicksort(nums, 0, nums.size() - 1, k);
//		return { nums.begin(),nums.begin() + k };
//	}
//
//	void quicksort(vector<int>& nums, int l, int r, int k)
//	{
//		if (l == r)
//		{
//			return;
//		}
//
//		// 1. 选基准元素
//		int key = getrandom(nums, l, r);
//		int left = l - 1, right = r + 1, i = l;
//
//		// 2. 三路划分
//		while (i < right)
//		{
//			if (nums[i] < key)
//			{
//				swap(nums[++left], nums[i++]);
//			}
//			else if (nums[i] == key)
//			{
//				i++;
//			}
//			else
//			{
//				swap(nums[--right], nums[i]);
//			}
//		}
//
//		// 3. 快速选择
//		int a = left - l + 1, b = (right - 1) - (left + 1) + 1;
//		if (a > k)
//		{
//			quicksort(nums, l, left, k);
//		}
//		else if (a + b >= k)
//		{
//			return;
//		}
//		else
//		{
//			quicksort(nums, right, r, k - a - b);
//		}
//	}
//
//	int getrandom(vector<int>& nums, int l, int r)
//	{
//		return nums[rand() % (r - l + 1) + l];
//	}
//
//	vector<int> v{ 2,3,1 };
//};
//
//int main()
//{
//	Solution s;
//	for (auto ch : s.getLeastNumbers(s.v, 2))
//	{
//		cout << ch << " ";
//	}
//	return 0;
//}

//int getrandom(vector<int>& nums, int l, int r)
//{
//	return nums[rand() % (r - l + 1) + l];
//}
//
//int quicksort(vector<int>& nums, int l, int r, int k)
//{
//	if (l == r)
//	{
//		return nums[l];
//	}
//
//	// 1. 选取中间元素
//	int key = getrandom(nums, l, r);
//	int left = l - 1, right = r + 1, i = l;
//
//	// 2. 三路划分
//	while (i < right)
//	{
//		if (nums[i] < key)
//		{
//			swap(nums[++left], nums[i++]);
//		}
//		else if (nums[i] == key)
//		{
//			i++;
//		}
//		else
//		{
//			swap(nums[--right], nums[i]);
//		}
//	}
//
//	// 3. 判断
//	int c = r - right + 1;
//	int b = (right - 1) - (left + 1) + 1;
//	if (c >= k)
//	{
//		return quicksort(nums, right, r, k);
//	}
//	else if (b + c >= k)
//	{
//		return key;
//	}
//	else
//	{
//		return quicksort(nums, l, left, k);
//	}
//}
//
//int findKthLargest(vector<int>& nums, int k)
//{
//	srand(time(NULL));
//	return quicksort(nums, 0, nums.size() - 1, k);
//}
//
//int main()
//{
//	vector<int> v{ 9,8,7,6,5,3,1 };
//	cout << findKthLargest(v, 2);
//	return 0;
//}



//int numssort(vector<int>& nums, int left, int right)
//{
//	int keyi = rand() % (right - left + 1) + left;
//	return nums[keyi];
//}
//
//void quicksort(vector<int>& nums, int begin, int end)
//{
//	if (begin >= end)
//	{
//		return;
//	}
//	int left = begin - 1;
//	int right = end + 1;
//	int i = begin;
//	int key = numssort(nums, begin, end);
//	while (i < right)
//	{
//		if (nums[i] < key)
//		{
//			swap(nums[++left], nums[i++]);
//		}
//		else if (nums[i] == key)
//		{
//			i++;
//		}
//		else
//		{
//			swap(nums[--right], nums[i]);
//		}
//	}
//	quicksort(nums, begin, left);
//	quicksort(nums, right, end);
//}
//
//void AdjustDown(vector<int>& nums, int size, int parent)
//{
//	int child = parent * 2 + 1;
//	while (child < size)
//	{
//		if (child + 1 < size && nums[child] < nums[child + 1])
//		{
//			child++;
//		}
//		if (nums[parent] < nums[child])
//		{
//			swap(nums[parent], nums[child]);
//			parent = child;
//			child = parent * 2 + 1;
//		}
//		else
//		{
//			break;
//		}
//	}
//}
//
//void HeapSort(vector<int>& nums, int size)
//{
//	for (int i = size - 1 - 1; i >= 0; i--)
//	{
//		AdjustDown(nums, size, i);
//	}
//
//	int end = size - 1;
//	while (end > 0)
//	{
//		swap(nums[0], nums[end]);
//		AdjustDown(nums, end, 0);
//		end--;
//	}
//}
//
//int main()
//{
//	srand(time(NULL));
//	vector<int> v{ 9,8,6,5,4,3,2,11 };
//	HeapSort(v, v.size());
//	for (auto ch : v)
//	{
//		cout << ch << " ";
//	}
//	return 0;
//}

//void sortColors(vector<int>& nums)
//{
//	int left = -1, right = nums.size(), i = 0;
//	while (i < right)
//	{
//		if (nums[i] == 0)
//		{
//			left++;
//			swap(nums[left], nums[i]);
//			i++;
//		}
//		else if (nums[i] == 1)
//		{
//			i++;
//		}
//		else
//		{
//			right--;
//			swap(nums[right], nums[i]);
//		}
//	}
//}
//
//void partsort(vector<int>& nums, int& begin, int& end, int key)
//{
//	int left = begin - 1, right = end + 1, i = begin;
//	while (i < right)
//	{
//		if (nums[i] < key)
//		{
//			left++;
//			swap(nums[left], nums[i]);
//			i++;
//		}
//		else if (nums[i] == key)
//		{
//			i++;
//		}
//		else
//		{
//			right--;
//			swap(nums[right], nums[i]);
//		}
//	}
//}
//
//void quicksort(vector<int>& nums, int& begin, int& end, int key)
//{
//	if (begin == end)
//	{
//		return;
//	}
//	partsort(nums, begin, end, key);
//
//}

//int numsrandom(vector<int>& nums, int left, int right)
//{
//	int keyi = rand() % (right - left + 1);
//	return nums[keyi];
//	//int keyi = rand() % (right - left + 1) + left;
//	//return nums[keyi];
//}
//
//
//void quicksort(vector<int>& nums, int l, int r)
//{
//	if (l >= r)
//	{
//		return;
//	}
//	int key = numsrandom(nums, l, r);
//	int i = l, left = l - 1, right = r + 1;
//	while (i < right)
//	{
//		if (nums[i] < key)
//		{
//			swap(nums[++left], nums[i++]);
//		}
//		else if (nums[i] == key)
//		{
//			i++;
//		}
//		else
//		{
//			swap(nums[--right], nums[i]);
//		}
//	}
//	quicksort(nums, l, left);
//	quicksort(nums, right, r);
//}
//
//
//vector<int> sortArray(vector<int>& nums)
//{
//	srand(time(0));
//	quicksort(nums, 0, nums.size() - 1);
//	return nums;
//}
//
//int main()
//{
//	vector<int> v = { 10,9,55,4,2,0,2,1,1,0 };
//	int begin = 0, end = v.size() - 1;
//	quicksort(v, begin, end);
//
//	for (auto ch : v)
//	{
//		cout << ch << " ";
//	}
//	return 0;
//}

//int numbers(int m)
//{
//    int num = 0;
//    for (int i = 0; i < 32; i++)
//    {
//        if (m != 0)
//        {
//            if ((m & 1) == 1)
//            {
//                num++;
//            }
//            m = m >> 1;
//        }
//        else
//        {
//            break;
//        }
//    }
//    return num;
//}
//
//vector<int> countBits(int n)
//{
//    vector<int> v;
//    for (int i = 0; i <= n; i++)
//    {
//        int ret = numbers(i);
//        v.push_back(ret);
//    }
//    return v;
//}

//int hammingDistance(int x, int y)
//{
//	int ret = 0;
//	for (int i = 0; i < 32; i++)
//	{
//		if ((x >> i & 1) != (y >> i & 1))
//		{
//			ret++;
//		}
//	}
//	return ret;
//}

//int getSum(int a, int b)
//{
//    // 无进位相加
//    a = a ^ b;
//    // 进位
//    b = (a & b) << 1;
//    while (b != 0)
//    {
//        a = a ^ b;
//        b = (a & b) << 1;
//    }
//    return a;
//}
// 001
// 010

//void sort(vector<int>& nums)
//{  //6,1,2,5,-1,-1
//	for (int i = 0; i < nums.size(); i++) 
//	{
//		while (nums[i] != -1 && nums[i] != i + 1)
//		{
//			swap(nums[i], nums[nums[i] - 1]);
//		}
//	}
//}

//string convert(string s, int numRows)
//{
//    vector<vector<char>> v(numRows, vector <char>(334));
//    int k = 0;
//    int i = 0;
//    while (k < s.size())
//    {
//        for (int j = 0; j < numRows && k < s.size(); j++)
//        {
//            v[j][i] = s[k++];
//        }
//        for (int m = numRows - 2; m > 0 && k < s.size(); m--)
//        {
//            v[m][++i] = s[k++];
//        }
//        i++;
//    }
//    string ans;
//    for (int i = 0; i < numRows; i++)
//    {
//        for (int j = 0; j < 334; j++)
//        {
//            if (v[i][j] != 0)
//            {
//                ans.push_back(v[i][j]);
//            }
//        }
//    }
//    return ans;
//}

//string countAndSay(int n)
//{
//	string ret = "1";
//	for (int i = 1; i < n; i++)
//	{
//		int left = 0, right = 0;
//		int count = 0;
//		string tmp;
//		while (right < ret.size())
//		{
//			while (ret[right] == ret[left])
//			{
//				right++;
//			}
//			count = right - left;
//			tmp += count + '0';
//			tmp += ret[left];
//			left = right;
//		}
//		ret = tmp;
//	}
//	return ret;
//}

//int main()
//{
//	string s1 = "hello";
//	s1.erase(0, 1);
//	cout << s1 << endl;
//
//	vector<int> v{ 6,1,2,5,-1,-1 };
//	//sort(v);
//	return 0;
//}

//int maxDepth(string s)
//{
//    int res = 0;
//    stack<int> stack;
//    for (auto ch : s)
//    {
//        if (ch == '(')
//        {
//            stack.push(1);
//            res = max(res, (int)stack.size());
//        }
//        if (ch == ')')
//        {
//            stack.pop();
//        }
//    }
//    return res;
//}


//struct ListNode
//{
//	int val;
//	ListNode* next;
//	ListNode(int x) 
//		: val(x)
//		, next(NULL) 
//	{}
//};
//
//
//ListNode* addTwoNumbers(ListNode* l1, ListNode* l2)
//{
//	if (l1 == nullptr)
//	{
//		return l2;
//	}
//	if (l2 == nullptr)
//	{
//		return l1;
//	}
//	ListNode* newhead = new ListNode(0);
//	ListNode* tail = newhead;
//	int ret = 0;
//	while (l1 && l2)
//	{
//		int sum = l1->val + l2->val + ret;
//		ret = sum / 10;
//		sum = sum % 10;
//		ListNode* newnode = new ListNode(sum);
//		tail->next = newnode;
//		tail = tail->next;
//	}
//	while (l1)
//	{
//		int sum = l1->val + ret;
//		ret = sum / 10;
//		sum = sum % 10;
//		ListNode* newnode = new ListNode(sum);
//		tail->next = newnode;
//		tail = tail->next;
//	}
//	while (l2)
//	{
//		int sum = l2->val + ret;
//		ret = sum / 10;
//		sum = sum % 10;
//		ListNode* newnode = new ListNode(sum);
//		tail->next = newnode;
//		tail = tail->next;
//	}
//	if (ret == 1)
//	{
//		ListNode* newnode = new ListNode(1);
//		tail->next = newnode;
//		tail = tail->next;
//	}
//	return newhead->next;
//}

//int pivotIndex(vector<int>& nums)
//{
//	// 前缀和数组 
//	vector<int> f(nums.size() + 1);
//	f[0] = 0;
//	for (int i = 1; i <= nums.size(); i++)
//	{
//		f[i] = f[i - 1] + nums[i - 1];
//	}
//
//	// 后缀和数组
//	vector<int> g(nums.size() + 1);
//	g[nums.size() - 1] = 0;
//	for (int i = nums.size() - 2; i >= 0; i--)
//	{
//		g[i] = g[i + 1] + nums[i + 1];
//	}
//
//	// 寻找
//	for (int i = 0; i < nums.size(); i++)
//	{
//		if (f[i] == g[i])
//		{
//			return i;
//		}
//	}
//	return -1;
//}

//vector<int> productExceptSelf(vector<int>& nums)
//{
//    int n = nums.size();
//    // 前缀和数组
//    vector<int> f(n);
//    f[0] = 1;
//    for (int i = 1; i < n; i++)
//    {
//        f[i] = f[i - 1] * nums[i - 1];
//    }
//    // f:1,1,2,6
//
//    // 后缀和数组
//    vector<int> g(n);
//    g[n - 1] = 1;
//    for (int i = n - 2; i >= 0; i--)
//    {
//        g[i] = g[i + 1] * nums[i + 1];
//    }
//    // g:24,12,4,1
//
//    // 返回数组
//    vector<int> res(n);
//    res[0] = g[0];
//    res[n - 1] = f[n - 1];
//    for (int i = 1; i < n - 1; i++)
//    {
//        res[i] = f[i] * g[i];
//    }
//    return res;
//}

//vector<vector<int>> matrixBlockSum(vector<vector<int>>& mat, int k)
//{
//    int m = mat.size();
//    int n = mat[0].size();
//    // 创建前缀和二维数组
//    vector<vector<int>> dp(m + 1, vector<int>(n + 1));
//    for (int i = 1; i <= m; i++)
//    {
//        for (int j = 1; j <= n; j++)
//        {
//            dp[i][j] = dp[i - 1][j] + dp[i][j - 1] - dp[i - 1][j - 1] + mat[i - 1][j - 1];
//        }
//    }
//
//    // 算数据
//    vector<vector<int>> ans(m + 1, vector<int>(n + 1));
//    for (int i = 0; i < m; i++)
//    {
//        for (int j = 0; j < n; j++)
//        {
//            int x1 = max(0, i - k) + 1, y1 = max(0, j - k) + 1;
//            int x2 = i + k + 1, y2 = j + k + 1;
//            ans[i][j] = dp[x2][y2] - dp[x2][y1 - 1] - dp[x1 - 1][y2] + dp[x1 - 1][y1 - 1];
//        }
//    }
//    return ans;
//}
//
//int main()
//{
//	int arr[] = { 1,2,3,4 };
//	int sz = sizeof(arr) / sizeof(arr[0]);
//	vector<int> v(arr, arr + sz);
//    matrixBlockSum(v);
//	return 0;
//}

//#include <iostream>
//#include <vector>
//using namespace std;

//int main()
//{
//	int m = 3, n = 4, q = 3;
//	cin >> m >> n >> q;
//	vector<vector<int>> v(m + 1,vector<int>(n+1));
//	// 数据输入
//	for (int i = 1; i <= m; i++)
//	{
//		for (int j = 1; j <= n; j++)
//		{
//			cin >> v[i][j];
//		}
//	}
//	// 处理dp数组
//	vector<vector<int>> dp(m + 1, vector<int>(n + 1));
//	for (int i = 1; i <= m; i++)
//	{
//		for (int j = 1; j <= n; j++)
//		{
//			dp[i][j] = dp[i - 1][j] + dp[i][j - 1] + v[i][j] - dp[i - 1][j - 1];
//		}
//	}
//	// 处理数据
//	while (q--)
//	{
//		int x1, y1, x2, y2;
//		cin >> x1 >> y1 >> x2 >> y2;
//		cout << dp[x2][y2] - dp[x2][y1-1] - dp[x1-1][y2] + dp[x1 - 1][y1 - 1] << endl;
//	}
//	return 0;
//}

//int main()
//{
//    int n, q;
//    cin >> n >> q;
//    vector<long long> v(n + 1);
//    for (int i = 1; i <= n; i++)
//    {
//        cin >> v[i];
//    }
//    vector<long long> dp(n + 1);
//    dp[0] = 0;
//    for (int i = 1; i <= n; i++)
//    {
//        dp[i] = dp[i - 1] + v[i];
//    }
//    while (q--)
//    {
//        int l, r;
//        cin >> l >> r;
//        cout << dp[r] - dp[l - 1] << endl;
//    }
//    return 0;
//}


//#include <bits/stdc++.h>
//using namespace std;
//
//int main()
//{
//    vector<long long> v;
//    int n, q;
//    cin >> n >> q;
//    v.reserve(n);
//    v.push_back(0);
//    for (int i = 1; i <= n; i++)
//    {
//        int m;
//        cin >> m;
//        v.push_back(m);
//    }
//    vector<long long> dp;
//    dp.reserve(n);
//    dp.push_back(0);
//    for (int i = 1; i <= n; i++)
//    {
//        long long tmp= dp[i - 1] + v[i];
//        dp.push_back(tmp);
//    }
//    while (q--)
//    {
//        int l, r;
//        cin >> l >> r;
//        cout << dp[r] - dp[l - 1] << endl;
//    }
//    return 0;
//}

//vector<int> searchRange(vector<int>& nums, int target)
//{
//    vector<int> v;
//    int left1 = 0, right1 = nums.size();
//    while (left1 < right1)
//    {
//        int mid1 = left1 + (right1 - left1) / 2;
//        if (nums[mid1] < target)
//        {
//            left1 = mid1 + 1;
//        }
//        else
//        {
//            right1 = mid1;
//        }
//    }
//    nums[left1] == target ? v.push_back(left1) : v.push_back(-1);
//
//    int left2 = 0, right2 = nums.size();
//    while (left2 < right2)
//    {
//        int mid2 = left2 + (right2 - left2 + 1) / 2;
//        if (nums[mid2] > target)
//        {
//            right2 = mid2 - 1;
//        }
//        else
//        {
//            left2 = mid2;
//        }
//    }
//    nums[right2] == target ? v.push_back(right2) : v.push_back(-1);
//    return v;
//}

//int main()
//{
//    int arr[] = { 1 };
//    int sz = sizeof(arr) / sizeof(arr[0]);
//    vector<int> v(arr, arr + sz);
//    vector<int> v1;
//    v1 = searchRange(v, 0);
//    for (auto ch : v1)
//    {
//        cout << ch << " ";
//    }
//    cout << endl;
//    return 0;
//}

//while (left <= right)
//{
//    int mid = left + (right - left) / 2;
//    if (nums[mid] == target)
//    {
//        return mid;
//    }
//    else if (nums[mid] < target)
//    {
//        left = mid + 1;
//    }
//    else
//    {
//        right = mid - 1;
//    }
//}

//int lengthOfLongestSubstring(string s)
//{
//    if (s.size() == 1)
//    {
//        return 1;
//    }
//    int left = 0, right = 0, hash[128] = { 0 }, ret = 0;
//    for (left = 0, right = 0; right < s.size(); right++)
//    {
//        // 进窗口
//        hash[s[right]]++;
//
//        // 判断
//        while (hash[s[right]] > 1)
//        {
//            ret = max(ret, right - left);
//            // 出窗口
//            hash[s[left++]]--;
//        }
//    }
//    return ret;
//}

//int longestOnes(vector<int>& nums, int k)
//{
//    int left = 0, right = 0, len = 0, ret = 0;
//    for (left = 0, right = 0; right < nums.size(); right++)
//    {
//        // 进窗口
//        if (nums[right] == 0)
//        {
//            ret++;
//        }
//
//        // 判断
//        if (ret > k)
//        {
//            // 出窗口
//            //while (nums[left++] != 0);
//            while (nums[left] != 0)
//            {
//                left++;
//            }
//            ret--;
//        }
//
//        len = max(len, right - left + 1);
//    }
//    return len;
//}

//int longestOnes(vector<int>& nums, int k)
//{
//    int left = 0, right = 0, len = 0, ret = 0;
//    for (left = 0, right = 0; right < nums.size(); right++)
//    {
//        // 进窗口
//        if (nums[right] == 0)
//        {
//            ret++;
//        }
//
//        // 判断
//        if (ret > k)
//        {
//            // 出窗口
//            //while (nums[left++] != 0);
//            while (nums[left] != 0)
//            {
//                left++;
//            }
//            ret--;
//        }
//
//        len = max(len, right - left + 1);
//    }
//    return len;
//}

//int totalFruit(vector<int>& fruits)
//{
//    int hash[10001] = { 0 }, kind = 0, len = 0;
//    for (int left = 0, right = 0; right < fruits.size(); right++)
//    {
//        // 进窗口
//        if (hash[fruits[right]] == 0)
//        {
//            kind++;
//        }
//        hash[fruits[right]]++;
//
//        // 判断
//        while (kind > 2)
//        {
//            // 出窗口
//            while (hash[fruits[left]] != 0)
//            {
//                hash[fruits[left]]--;
//                if (hash[fruits[left]] == 0)
//                {
//                    kind--;
//                    break;
//                }
//                left++;
//            }
//            left++;
//            //hash[fruits[left]]--;
//            //if (hash[fruits[left]] == 0)
//            //{
//            //    kind--;
//            //}
//            //left++;
//        }
//
//        len = max(len, right - left + 1);
//    }
//    return len;
//}

//bool hashcmp(int a[], int b[], int sz)
//{
//	for (int i = 0; i < sz; i++)
//	{
//		if (a[i] != b[i])
//			return false;
//	}
//	return true;
//}
//
//vector<int> findAnagrams(string s, string p)
//{
//	vector<int> v;
//	int hash1[26] = { 0 };
//	int hash2[26] = { 0 };
//	// p内数据扔到hash1中
//	for (auto ch : p)
//	{
//		hash1[ch - 'a']++;
//	}
//
//	int left = 0, right = 2;
//	for (int i = left; i <= right; i++)
//	{
//		hash2[s[i] - 'a']++;
//	}
//
//	while (right < s.size())
//	{
//		if (hashcmp(hash1, hash2, 26))
//		{
//			v.push_back(left);
//		}
//		hash2[s[left] - 'a']--;
//		//hash2[s[right++] - 'a']--;
//		left++, right++;
//		
//		//hash2[s[left] - 'a']++;
//		hash2[s[right] - 'a']++;
//	}
//	return v;
//}
//
//int main()
//{
//	//string s1 = "au";
//	int arr[] = { 3,3,3,1,2,1,1,2,3,3,4 };
//	int sz = sizeof(arr) / sizeof(arr[0]);
//	vector<int> v(arr, arr + sz);
//	string s1 = "cbaebabacd";
//	string s2 = "abc";
//	findAnagrams(s1, s2);
//	return 0;
//}

//#include <stdio.h>
//#include <stdlib.h>
//#include <string.h>
//
//typedef struct Node {
//    char ch;
//    int freq;
//    struct Node* left, * right;
//} Node;
//
//Node* initHuffmanTree(char* s) {
//    // 统计字符频度
//    int freq[256] = { 0 };
//    for (int i = 0; i < strlen(s); i++) {
//        freq[s[i]]++;
//    }
//
//    // 创建叶子节点
//    Node* nodes[256] = { NULL };
//    for (int i = 0; i < 256; i++) {
//        if (freq[i] > 0) {
//            nodes[i] = (Node*)malloc(sizeof(Node));
//            nodes[i]->ch = i;
//            nodes[i]->freq = freq[i];
//            nodes[i]->left = nodes[i]->right = NULL;
//        }
//    }
//
//    // 构建哈夫曼树
//    while (1) {
//        int min1 = -1, min2 = -1;
//        for (int i = 0; i < 256; i++) {
//            if (nodes[i] != NULL) {
//                if (min1 == -1 || nodes[i]->freq < nodes[min1]->freq) {
//                    min2 = min1;
//                    min1 = i;
//                }
//                else if (min2 == -1 || nodes[i]->freq < nodes[min2]->freq) {
//                    min2 = i;
//                }
//            }
//        }
//
//        if (min2 == -1) break;
//        Node* newNode = (Node*)malloc(sizeof(Node));
//        newNode->ch = '\0';
//        newNode->freq = nodes[min1]->freq + nodes[min2]->freq;
//        newNode->left = nodes[min1];
//        newNode->right = nodes[min2];
//        nodes[min1] = newNode;
//        nodes[min2] = NULL;
//    }
//
//    return nodes[0];
//}
//
//void createTable(Node* root, char* table[], int* code, int size) {
//    if (root == NULL) return;
//    if (root->left == NULL && root->right == NULL) {
//        table[*code] = root->ch;
//        (*code)++;
//    }
//    createTable(root->left, table, code, size);
//    createTable(root->right, table, code, size);
//}
//
//void encoding(Node* root, char* str, int* code, int size) {
//    if (root == NULL) return;
//    if (root->left == NULL && root->right == NULL) {
//        str[*code] = '\0';
//        printf("%c: %s", root->ch, str);
//    }
//    encoding(root->left, str, code, size);
//    encoding(root->right, str, code, size);
//}
//
//void decoding(Node* root, char* str, int size) {
//    Node* cur = root;
//    while (*str != '\0') {
//        if (*str == '0') {
//            cur = cur->left;
//        }
//        else {
//            cur = cur->right;
//        }
//        if (cur->left == NULL && cur->right == NULL) {
//            printf("%c", cur->ch);
//            str++;
//        }
//    }
//    printf(" ");
//}
//
//int main() {
//    char s[] = "thisprogramismyfavourite";
//    int size = strlen(s);
//    Node* root = initHuffmanTree(s);
//    char table[256][32];
//    int code[256] = { 0 };
//    createTable(root, table, code, size);
//    char str[1000];
//    encoding(root, str, code, size);
//    printf("编码后的字符串： %s", str);
//    decoding(root, str, size);
//    return 0;
//}


//int triangleNumber(vector<int>& nums)
//{
//	sort(nums.begin(), nums.end());
//	int cut = 0;
//	for (int max = nums.size() - 1; max >= 2; max--)
//	{
//		int left = 0, right = max - 1;
//		while (left < right)
//		{
//			if (nums[left] + nums[right] > nums[max])
//			{
//				cut += right - left;
//				right--;
//			}
//			else
//			{
//				left++;
//			}
//		}
//	}
//	return cut;
//}

//vector<int> twoSum(vector<int>& nums, int target)
//{
//    vector<int> v;
//    int left = 0;
//    int right = nums.size() - 1;
//    if (nums[right] > target)
//    {
//        right--;
//    }
//    for (int i = 0; i <= right; i++)
//    {
//        for (int j = i + 1; j <= right; j++)
//        {
//            if (nums[i] + nums[j] == target)
//            {
//                v.push_back(nums[i]);
//                v.push_back(nums[j]);
//                return v;
//            }
//        }
//    }
//    return v;
//}

//vector<vector<int>> threeSum(vector<int>& nums)
//{
//    vector<vector<int>> v;
//    sort(nums.begin(), nums.end());
//    for (int max = nums.size() - 1; max >= 2; max--)
//    {
//        int left = 0;
//        int right = max - 1;
//        if (nums[0] + nums[max] > 0)
//        {
//            continue;
//        }
//        while (left < right)
//        {
//            if (nums[left] + nums[right] + nums[max] == 0)
//            {
//                v.push_back({ nums[left],nums[right],nums[max] });
//                left++;
//            }
//            else if (nums[left] + nums[right] + nums[max] > 0)
//            {
//                right--;
//            }
//            else
//            {
//                left++;
//            }
//        }
//    }
//    return v;
//}

//vector<vector<int>> threeSum(vector<int>& nums)
//{
//    vector<vector<int>> v;
//    // 排序
//    sort(nums.begin(), nums.end());
//
//    for (int i = 0; i < nums.size();)
//    {
//        // 优化
//        if (nums[i] > 0)
//        {
//            break;
//        }
//        int left = i + 1, right = nums.size() - 1;
//        while (left < right)
//        {
//            if (nums[left] + nums[right] + nums[i] > 0)
//            {
//                right--;
//            }
//            else if (nums[left] + nums[right] + nums[i] < 0)
//            {
//                left++;
//            }
//            else
//            {
//                v.push_back({ nums[i],nums[left],nums[right] });
//                left++;
//                right--;
//            }
//
//            // 去重1
//            while (left < right && nums[left] == nums[left - 1])
//            {
//                left++;
//            }
//            while (left < right && nums[right] == nums[right + 1])
//            {
//                right--;
//            }
//            // 去重2
//            i++;
//            while (nums[i] == nums[i - 1])
//            {
//                i++;
//            }
//        }
//    }
//    return v;
//}

//vector<vector<int>> fourSum(vector<int>& nums, int target)
//{
//    vector<vector<int>> v;
//    // 排序
//    sort(nums.begin(), nums.end());
//
//    // 控制第一个数
//    for (int i = 0; i < nums.size();)
//    {
//        // 控制第二个数
//        for (int j = i + 1; j < nums.size();)
//        {
//            // 在区间内找
//            int left = j + 1, right = nums.size() - 1;
//            while (left < right)
//            {
//                if (nums[i] + nums[j] + nums[left] + nums[right] > target)
//                {
//                    right--;
//                }
//                else if (nums[i] + nums[j] + nums[left] + nums[right] < target)
//                {
//                    left++;
//                }
//                else
//                {
//                    v.push_back({ nums[i],nums[j],nums[left],nums[right] });
//                    left++;
//                    right--;
//
//                    // 去重
//                    while (left < right && nums[left] == nums[left - 1])
//                    {
//                        left++;
//                    }
//                    while (left < right && nums[right] == nums[right + 1])
//                    {
//                        right--;
//                    }
//                }
//            }
//
//            // 对固定数去重
//            j++;
//            while (j < nums.size() && nums[j] == nums[j - 1])
//            {
//                j++;
//            }
//        }
//        i++;
//        while (i < nums.size() && nums[i] == nums[i - 1])
//        {
//            i++;
//        }
//    }
//    return v;
//}

//int minSubArrayLen(int target, vector<int>& nums)
//{
//	int left = 0, right = 0;
//	int sum = nums[0], len = 0;
//	while (right < nums.size())
//	{
//		if (sum < target)
//		{
//			right++;
//			if (right < nums.size())
//				sum = sum + nums[right];
//		}
//		else
//		{
//			break;
//		}
//	}
//	if (sum < target)
//	{
//		return 0;
//	}
//	len = right - left + 1;
//	while (right < nums.size())
//	{
//		if (sum >= target)
//		{
//			sum -= nums[left];
//			left++;
//			len--;
//		}
//		else
//		{
//			right++;
//			if (right < nums.size())
//			{
//				sum += nums[right];
//				len++;
//			}
//		}
//	}
//	return right - left + 1;
//}
//
//int main()
//{
//	int arr[] = { 5,1,3,5,10,7,4,9,2,8 };
//	int sz = sizeof(arr) / sizeof(arr[0]);
//	vector<int> v(arr, arr + sz);
//	int num = 15;
//	cout << minSubArrayLen(num, v) << endl;
//	return 0;
//}

//int main()
//{
//	int arr[] = { -2,-1,0,0,1,2 };
//	int sz = sizeof(arr) / sizeof(arr[0]);
//	vector<int> v(arr, arr + sz);
//	vector<vector<int>> vv = fourSum(v,0);
//	for (int i = 0; i < vv.size(); i++)
//	{
//		for (int j = 0; j < vv[i].size(); j++)
//		{
//			cout << vv[i][j] << " ";
//		}
//		cout << endl;
//	}
//}

//int maxArea(vector<int>& height)
//{
//    int left = 0;
//    int right = height.size() - 1;
//    int v = 0;
//    int max = 0;
//    while (left < right)
//    {
//        v = min(height[left], height[right]) * (right - left);
//        if (v > max)
//        {
//            max = v;
//        }
//        if (height[left] < height[right])
//        {
//            left++;
//        }
//        else
//        {
//            right--;
//        }
//    }
//    return max;
//}
//
//int main()
//{
//    int arr[] = { 1,8,6,2,5,4,8,3,7 };
//    int sz = sizeof(arr) / sizeof(arr[0]);
//    vector<int> v(arr, arr + sz);
//    cout << maxArea(v);
//}

//int CalRes(int num)
//{
//    int res = 0;
//    while (num)
//    {
//        res += (num % 10) * (num % 10);
//        num = num / 10;
//    }
//    return res;
//}
//bool isHappy(int n)
//{
//    int num = n;
//    cout << n << " ";
//    int slow = CalRes(num);
//    int fast = CalRes(CalRes(num));
//    while (slow != fast)
//    {
//        cout << slow << " ";
//        slow = CalRes(slow);
//        fast = CalRes(CalRes(fast));
//    }
//    if (fast == 1)
//    {
//        return true;
//    }
//    else
//    {
//        return false;
//    }
//}

//int main()
//{
//    cout << isHappy(2) << endl;
//}

//2
//4
//16
//37
//52
//29
//85
//